Сегментация методом «Водораздел»

Водораздел (в математической морфологии) – метод сегментации изображений (районирования территории, представленной растром; кластеризация регулярной ТОС).

Изображение для сегментации должно содержать только одно свойство (монохромное изображение). Тогда изображение принимается за поверхность, а высота поверхности в каждой точке равна значению свойства. Строится разбиение по минимумам этой поверхности: каждому локальному минимуму ставится в соответствие свой кластер, а для точек, не являющихся локальным минимумом, строится траектория спуска к локальному минимому по направлению антиградиента (по направлению, по которому «стекала бы капля воды»), и соответствующий объект приписывается кластеру, соответствующему данному минимуму. Построенные кластеры называются бассейнами.

На втором этапе над разбиением на кластеры строится иерархическая кластеризация. В основе такого разбиения – включение бассейнов через «переливание» воды из одних «бассейнов» в другие при их «заполнении водой» [2].

Для сегментации изображений/сеток по похожести (близости свойств) следует произвести расчёт модуля градиента для каждого интересующего свойства, после чего вручную записать сумму модулей градиентов в новое свойство (возможно, взвешенную сумму), например, через калькулятор свойств. При этом окно градиента фактически задаёт масштаб сегментации: чем меньше окно, тем больше будет построено кластеров иерархического разбиения. Хотя эти кластеры потом можно объединить при работе с дендрограммой, результат зависит от размера окна градиента и может отличаться качественно (большие окна ведут к более гладким границам кластеров/сегментов).

Алгоритм

Для регулярной прямоугольной сетки (то есть, регулярной ТОС 2D и 3D) каждому объекту присваивается номер кластера в соответствии со следующим правилом:

1. Если объект – локальный минимум, то ему ставится в соответствие номер, отличный от номера любого другого локального минимума.
2. Иначе для объекта среди его ближайших соседей выбирается объект, имеющий минимальное значение свойства, и ставится в соответствие уже его номер.
   1. Если имеется несколько соседних вершин, имеющих минимальное значение свойства, то выбор осуществляется произвольно (выбор не определён).

Множество ближайших соседей образуется из объектов, к которым можно перейти за один шаг по осям (то есть, имеющие значение номера профиля либо пикета, отличающиеся на единицу), а также объекты, к которым можно дойти за один шаг по диагонали, но с весом ${\displaystyle 1/\sqrt{2}}$. Для 3D ТОС есть 2 типа диагоналей – в плоскости и в пространстве; последние имеют вес ${\displaystyle 1/\sqrt{3}}$. Такое отношение соседства с такими весами делает результирующую картину более-менее симметричную и близкую к инвариантной по повороту растра на углы, отличные от кратных 90 градусам; при этом наблюдается максимальное отличие при повороте на 22,5 градуса.

Рассмотренная выше схема позволяет реализовать алгоритм [1] с вычислительной сложностью O(N), где N – количество объектов в ТОС, и она хорошо приближает описанный метод. Для более точно определённого метода пункт 2 переформулируется так, чтобы уменьшить неопределённость при выборе соседа из подмножества соседних с минимальным значением свойства. В этом случае рассматривается множество M допустимых путей до достижимых локальных минимумов, и выбирается лексикографически минимальный путь. Конечно, если лексикографически эквивалентных путей несколько, то неопределённость остаётся, но она значительно уменьшается. К сожалению, для такой схемы неизвестен эффективный линейный алгоритм.

Параметры

Алгоритм не имеет параметров. Но надо помнить, что он работает только с одним свойством, и в списке свойств следует выбирать только одно свойство. Если выбрано больше одного свойства, будет использовано первое выбранное.

Ссылки на литературу

1. J. Cousty, G. Bertrand, L. Najman and M. Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8) pp. 1362-1374, 2009,

2. Laurent Najman, Michel Schmitt. Geodesic Saliency of Watershed Contours and Hierarchical Seg-mentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electricaland Electronics Engineers, 1996, 18 (12), pp.1163-1173.